#include <iostream>

struct Node
{
    char _value;
    Node *_left_node;
    Node *_right_node;
    Node *_parent;

    Node(char value)
        : _value(value), _left_node(nullptr), _right_node(nullptr), _parent(nullptr) {}
};

Node *FindNext(Node *node)
{
    if (node == nullptr)
        return nullptr;

    if (node->_right_node != nullptr)
    {
        // 找右子树的最左节点
        Node *ret = node->_right_node;
        while (ret->_left_node != nullptr)
            ret = ret->_left_node;
        return ret;
    }
    else
    {
        Node *parent = node->_parent;
        
        // 找到一个父节点的左边是当前节点的位置，返回父节点
        while (parent != nullptr && parent->_right_node == node)
        {
            node = parent;
            parent = parent->_parent;
        }
        return parent;
    }
    return nullptr;
}

void Test1()
{

    Node *node1 = new Node('a');
    Node *node2 = new Node('b');
    Node *node3 = new Node('c');
    Node *node4 = new Node('d');
    Node *node5 = new Node('e');
    Node *node6 = new Node('f');
    Node *node7 = new Node('g');
    Node *node8 = new Node('h');
    Node *node9 = new Node('i');

    node1->_parent = nullptr;
    node1->_left_node = node2;
    node1->_right_node = node3;

    node2->_parent = node1;
    node2->_left_node = node4;
    node2->_right_node = node5;

    node3->_parent = node1;
    node3->_left_node = node6;
    node3->_right_node = node7;

    node4->_parent = node2;

    node5->_parent = node2;
    node5->_left_node = node8;
    node5->_right_node = node9;

    node6->_parent = node3;
    node7->_parent = node3;
    node8->_parent = node5;
    node9->_parent = node5;

    std::cout << FindNext(node2)->_value << std::endl;
    std::cout << FindNext(node4)->_value << std::endl;
    std::cout << FindNext(node8)->_value << std::endl;
    if (FindNext(node7) != nullptr)
    {
        std::cout << FindNext(node7)->_value << std::endl;
    }
    else
    {
        std::cout << "nullptr" << std::endl;
    }
}

void Test2()
{

    Node *node1 = new Node('a');
    Node *node2 = new Node('b');
    Node *node3 = new Node('c');
    Node *node4 = new Node('d');

    node1->_parent = nullptr;
    node1->_left_node = node2;

    node2->_parent = node1;
    node2->_left_node = node3;

    node3->_parent = node2;
    node3->_left_node = node4;

    node4->_parent = node3;

    std::cout << FindNext(node2)->_value << std::endl;
    std::cout << FindNext(node4)->_value << std::endl;
}

void Test3()
{

    Node *node1 = new Node('a');
    Node *node2 = new Node('b');
    Node *node3 = new Node('c');
    Node *node4 = new Node('d');

    node1->_parent = nullptr;
    node1->_right_node = node2;

    node2->_parent = node1;
    node2->_right_node = node3;

    node3->_parent = node2;
    node3->_right_node = node4;

    node4->_parent = node3;

    std::cout << FindNext(node2)->_value << std::endl;
    if (FindNext(node4) != nullptr)
    {
        std::cout << FindNext(node4)->_value << std::endl;
    }
    else
    {
        std::cout << "nullptr" << std::endl;
    }
}

void Test4()
{
    Node *node1 = new Node(1);

    if (FindNext(node1) != nullptr)
    {
        std::cout << FindNext(node1)->_value << std::endl;
    }
    else
    {
        std::cout << "nullptr" << std::endl;
    }
}

int main()
{
    Test1();
    Test2();
    Test3();
    Test4();
    return 0;
}